1. Field of the Invention
The present invention relates to reverse mapping of memory to data structure references, such as, for example, page table entries.
2. Related Art
In computer systems, a data structure can reference a page of data by referencing, or pointing to, the physical location of the data. For example, in a virtual memory mapping scheme, page table data structures store virtual memory address-to-physical memory address translations. Page tables include page table entries that reference mapped pages of memory. When activity affects a page of memory, page table entries that reference the page of memory must be updated or deleted.
Activity that can affect a page of memory includes moving the data in the memory to another location, such as hardware-based page migration. If the data is moved from a first page of memory to a second page of memory, any references to the page, such as page table entries that referenced, or mapped, the first page of memory must be updated to reference the second page of memory. However, there is currently no easy way to identify all of the references that need to be updated.
Activity that can affect a page of memory also includes delete operations and virtual cache coherency operations. For example, a virtual cache coherency scheme can, at times, require that a page of data not be mapped to more than one virtual address at a time. When this requirement is encountered, it is necessary to delete or invalidate all but one page table entries that map the page of memory to different virtual addresses. Virtual cache coherency is discussed in Schimmel, UNIX Systems for Modern Architectures, Symmetric Multiprocessing and Caching for Kernel Programmers, Addison-Wesley, at, for example, pp. 59-81 (1994), incorporated herein in its entirety by reference.
Activity that can affect a page of memory also includes file truncations. Existing systems handle file truncation by associating a linked list with a data structure that represents a file. The linked list identifies each user that mapped a portion of the file, such as page table addresses that map a portion of the file. When a portion of a file is truncated, the linked list is searched for users of the truncated portion so that associated page table entries can be deleted. Existing systems perform virtual cache coherency operations by searching the linked list described above and deleting page table entries as necessary. However, the linked lists can become very large and, hence, time consuming to search.
Activity that can affect a page of memory also includes paging activity such as page aging and page out operations. In a virtual memory paging system, there are typically more virtual pages than can fit in memory. Sometimes, virtual pages must be removed from memory to make room for others. A page aging system can be used to determine which pages to remove, by determining which pages are no longer in use. For example, a page aging system can turn off a valid bit in each page table entry that refers to a physical page. When a process refers to a page table entry that has a valid bit turned off a page fault occurs. The page fault can then be used to determine that the page that is referred to by the page table entry is still in use. The valid bit for that page table entry can then be turned back on. Pages that are referenced by page table entries that are not referenced again are candidates for removal.
When a page is identified for removal, a page out operation is used to eliminate page table entries that refer to page. A page out operation must identify all page table entries that reference the page and clear the page table entry. Currently, there is no fast and efficient way to identify page table entries that refer to physical pages and thus no fast and efficient way to perform page aging and page out operations.
Copies of page table entries can be cached in hardware items such as translational look-aside buffers (TLBs). Thus, when activity affects the page of memory, cached copies of page table entries that reference the page of memory must also be updated or deleted.
Existing systems maintain TLB coherence by broadcasting TLB flush commands to every TLB in a system, whenever any page table entry is changed or invalidated. This results in a large number of TLB misses because a large number of valid translations are unnecessarily invalidated.
UNIX System V, release 4, employs a hardware address translation (HAT) layer to set up page tables and associative memory entries. The HAT layer includes support functions for page table entries. For example, a hat.sub.-- free() instruction removes all of the page table entries that are associated with an address space. The function is called when an address space is being deleted. When this function is invoked, all of the page table entries that are associated with the HAT structure for the address space are set to zero (i.e., invalidated). For additional information on UNIX System V, Release 4, see "The Magic Garden Explained, The Internals of UNIX System V Release 4, An Open Systems Design," by Berny Goodheart and James Cox, Prentice Hall, 1994. For specific details of UNIX System V, Release 4, HAT layer, see The Magic Garden Explained, chapter 3 and pages 96-105.
Thus, existing methods for identifying and updating or deleting references to mapped pages of memory are inadequate.
What is needed is a system, method and computer program product for identifying data structures that reference a page of memory and for updating or removing the references when the referenced data is moved or deleted.